#pragma once

#include "TypeDefin.h"
#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"

using namespace std;
/*HJJ QQ479287006
 *列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。



示例 1：


输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
 * */
//string serialize(TreeNode* root) {
//    //层次遍历
//    queue<TreeNode*> q;
//    if (!root)
//        return "";
//
//    q.push(root);
//
//    string  res="";
//
//    while (!q.empty())
//    {
//        int sizer=q.size();
//        TreeNode* t=q.front();
//        q.pop();
//        for (int i = 0; i <sizer ; ++i) {
//            res=res+ to_string(t->val)+"," ;
//            if (t->left)
//                q.push(t->left);
//            if (t->right)
//                q.push(t->right);
//        }
//
//
//    }
//
//
//    return res;
//
//
//}
////二叉树插入
////返回跟节点  然后插入
//TreeNode* insertBST(TreeNode*& root,int val)
//{
//    if (root== nullptr)
//        return new TreeNode(val);
//
//    if (root->val<val)
//    {
//        root->right= insertBST(root->right,val);
//    }else if (root->val>val)
//    {
//        root->left= insertBST(root->left,val);
//    }
//
//
//    return root;
//}
//TreeNode* reet;
//void deserialize_r(string& data,int start_index,TreeNode*& root) {
//
//    if (start_index>=data.size())
//    {
//        return;
//    }
//
//    if (root== nullptr)
//    {
//        int i=data.find_first_of(",",start_index);
//        //123,
//        string temp=data.substr(start_index,i-start_index);
//        root= insertBST(root, stoi(temp));
//        reet=root;
//        // root=new TreeNode(stoi(temp));
//        start_index=i+1;
//    }
//
//    if (start_index<data.size())
//    {
//        int i=data.find_first_of(",",start_index);
//        string temp=data.substr(start_index,i-start_index);
//        root= insertBST(root, stoi(temp));
//        start_index=i+1;
//        deserialize_r(data,start_index,reet);
//    }
//
//}
//
//
//// Decodes your encoded data to tree.
////
//TreeNode* deserialize(string data) {
//   // data.pop_back();
//    TreeNode* root= nullptr;
//    deserialize_r(data,0,root);
//    return root;
//}


//这个题我理解错了我原来是以为层次遍历
// Encodes a tree to a single string.
string serialize(TreeNode *root) {
    if (root == NULL)
        return "#_";
    string res = to_string(root->val) + "_";
    res += serialize(root->left);
    res += serialize(root->right);
    return res;
}

// Decodes your encoded data to tree.
TreeNode *deserialize(string data) {
    std::stringstream ss(data);
    std::string item;
    queue<string> q;
    while (std::getline(ss, item, '_'))
        q.push(item);
    return helper(q);
}

TreeNode *helper(queue<string> &q) {
    string val = q.front();
    q.pop();
    if (val == "#")
        return NULL;
    TreeNode *head = new TreeNode(stoi(val));
    head->left = helper(q);
    head->right = helper(q);
    return head;
}